def find_substring(str1, pattern):
  start = 0 
  matched = 0
  pattern_map = {}
  smallest_str = ""
  smallest_length = len(str1)

  for i in pattern:
    if i not in pattern_map:
      pattern_map[i] = 0
    pattern_map[i] += 1

  for end in range(len(str1)):
    right = str1[end]
    if right in pattern:
      pattern_map[right] -= 1
      if pattern_map[right] == 0:
        matched += 1
    
    while(matched == len(pattern_map)):
      left = str1[start] 
      if left in pattern:
        if(pattern_map[left] == 0):
          matched -= 1
        pattern_map[left] += 1
      if(end-start+1)<smallest_length:
        smallest_str = str1[start:end+1]
        smallest_length = end-start+1
      start += 1

  # TODO: Write your code here
  return smallest_str

def main():
  print(find_substring("aabdec", "abc"))
  print(find_substring("abdbca", "abc"))
  print(find_substring("adcad", "abc"))

main()
